Edmonds- Karp Algorithm Algorithm
The Edmonds-Karp Algorithm is a specific implementation of the Ford-Fulkerson method, used for finding the maximum flow in a flow network. Developed by Jack Edmonds and Richard M. Karp in 1972, this algorithm uses a breadth-first search (BFS) approach to find the augmenting paths in the network, which in turn helps to optimize the overall complexity of the algorithm. The maximum flow problem aims to find the maximum amount of flow that can be sent from a source node to a sink node in a given network, subject to flow constraints on each edge.
The key idea behind the Edmonds-Karp Algorithm is to repeatedly find the shortest augmenting path (in terms of the number of edges) from the source to the sink using a BFS, then augment the flow along that path. This process is repeated until no more augmenting paths can be found. The algorithm guarantees that the search for augmenting paths will stop after a finite number of iterations, ensuring the termination and optimality of the solution. The Edmonds-Karp Algorithm has a worst-case time complexity of O(V^3 * E), where V is the number of vertices and E is the number of edges in the flow network. This makes it an efficient and widely used algorithm for solving various applications, such as transportation, job scheduling, and network connectivity problems, among others.
/*
Petar 'PetarV' Velickovic
Algorithm: Edmonds-Karp Algorithm
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 500
#define INF 987654321
using namespace std;
typedef long long lld;
struct Node
{
vector<int> adj;
};
Node graf[MAX_N];
bool mark[MAX_N];
int cap[MAX_N][MAX_N];
int parent[MAX_N];
int v, e;
int s, t;
//Edmonds-Karpov algoritam za nalazenje maksimalnog protoka izmedju dva cvora u grafu
//Moze se koristiti i za nalazenje maksimalnog matchinga
//Slozenost: O(V * E^2)
inline int BFS()
{
int ret = 0;
for (int i=1;i<=v;i++) parent[i] = 0;
queue<int> bfs_queue;
queue<int> minCapacity;
parent[s] = -1;
bfs_queue.push(s);
minCapacity.push(INF);
while (!bfs_queue.empty())
{
int xt = bfs_queue.front();
int mt = minCapacity.front();
bfs_queue.pop();
minCapacity.pop();
for (int i=0;i<graf[xt].adj.size();i++)
{
int xt1 = graf[xt].adj[i];
if (cap[xt][xt1] > 0 && parent[xt1] == 0)
{
bfs_queue.push(xt1);
minCapacity.push(min(mt,cap[xt][xt1]));
parent[xt1] = xt;
if (xt1 == t)
{
ret = min(mt, cap[xt][xt1]);
break;
}
}
}
}
if (ret > 0)
{
int currNode = t;
while (currNode != s)
{
cap[parent[currNode]][currNode] -= ret;
cap[currNode][parent[currNode]] += ret;
currNode = parent[currNode];
}
}
return ret;
}
inline int EdmondsKarp()
{
int flow = 0;
while (true)
{
int currFlow = BFS();
if (currFlow == 0) break;
else flow += currFlow;
}
return flow;
}
int main()
{
v = 4, e = 5;
s = 1, t = 4;
graf[1].adj.push_back(2);
graf[2].adj.push_back(1);
cap[1][2] = 40;
graf[1].adj.push_back(4);
graf[4].adj.push_back(1);
cap[1][4] = 20;
graf[2].adj.push_back(4);
graf[4].adj.push_back(2);
cap[2][4] = 20;
graf[2].adj.push_back(3);
graf[3].adj.push_back(2);
cap[2][3] = 30;
graf[3].adj.push_back(4);
graf[4].adj.push_back(3);
cap[3][4] = 10;
printf("%d\n",EdmondsKarp());
return 0;
}
